﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace DataStuctureStudy.Recursives
{
    class TriangleTest
    {
        public static int Triangle(int n)
        {
            // 地址：2
            if (n == 1)
            {
                // 地址：4
                return n;
            }

            /*   
             *   地址：4  地址：3
             *     /      /
             *    /      /
             *   /      /            */
            return n + Triangle(n - 1);
        }

        private class StackFrame
        {
            public int N;
            public int ReturnAddress;
        }

        public static int Triangle2(int n)
        {
            var stack = new Stack<StackFrame>();
            var currentReturnValue = 0;
            var currentAddress = 1;

            while (true)
            {
                switch (currentAddress)
                {
                    case 1:
                        {
                            stack.Push(new StackFrame
                            {
                                N = n,
                                ReturnAddress = 5
                            });
                            currentAddress = 2;
                        }
                        break;
                    case 2:
                        {
                            var frame = stack.Peek();
                            if (frame.N == 1)
                            {
                                currentReturnValue = 1;
                                currentAddress = 4;
                            }
                            else
                            {
                                stack.Push(new StackFrame
                                {
                                    N = frame.N - 1,
                                    ReturnAddress = 3
                                });
                                currentAddress = 2;
                            }
                        }
                        break;
                    case 3:
                        {
                            var frame = stack.Peek();
                            currentReturnValue = frame.N + currentReturnValue;
                            currentAddress = 4;
                        }
                        break;
                    case 4:
                        {
                            currentAddress = stack.Pop().ReturnAddress;
                        }
                        break;
                    case 5:
                        {
                            return currentReturnValue;
                        }
                }
            }
        }
    }
}
